package com.transfar.lib;


import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class ShuDu {
    private final static Object[][] test = new Object[][]{
            {0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0}
    };

    public static void main(String[] args) {

        Row[][] ques = new Row[rules.length()][rules.length()];
        for (int i = 0; i < rules.length(); i++) {
            for (int k = 0; k < rules.length(); k++) {
                Row item = ques[i][k] = new Row(que[i][k], i, k);

                System.out.print(item.loc() + "<" + item.value + ">" + item.sqrLoc() + "  ");
            }
            System.out.println();
        }

        writeSD();
    }

    private static void writeSD() {
        Row[][] ques = new Row[rules.length()][rules.length()];
        for (int i = 0; i < que.length; i++) {
            for (int k = 0; k < que[i].length; k++) {
                ques[i][k] = new Row(que[i][k], i, k);
                Row item = ques[i][k];
                if (k % 3 == 0) {
                    System.out.print("  ");
                }
                System.out.print("  " + item.value + "  ");
            }
            if ((i - 2) % 3 == 0) System.out.println();
            System.out.println();
        }
        int tag = 0;
        for (int all = 0; all < 10; all++) {
            boolean hasChange = false;
            for (int m = 0; m < 10; m++) {
                boolean hasChangeOne = writeOne(ques, ++tag);
                System.out.println();
                if (hasChangeOne) {
                    System.out.println("=========================writeOne" + (tag) + "=======================");
                    hasChange = true;
                    printTag(ques, tag, "[", "]");
                }
                if (!hasChangeOne) {
                    break;
                }
            }
            for (int m = 0; m < 10; m++) {
                boolean hasChangeTwo = writeTwo(ques, ++tag);
                System.out.println();
                if (hasChangeTwo) {
                    System.out.println("========================writeTwo" + tag + "========================");
                    hasChange = true;
                    printTag(ques, tag, "{", "}");
                }
                if (!hasChangeTwo) {
                    break;
                }
            }
            for (int m = 0; m < 10; m++) {
                boolean hasChangeThree = writeThree(ques, ++tag);
                System.out.println();
                if (hasChangeThree) {
                    System.out.println("========================writeThree" + tag + "========================");
                    hasChange = true;
                    printTag(ques, tag, "<", ">");
                }
                if (!hasChangeThree) {
                    break;
                }
            }
            if (!hasChange) {
                System.out.println("ShuDu-96:" + isOk(ques));
                break;
            }
        }
    }

    private static boolean writeThree(Row[][] ques, int tag) {
        boolean res = false;
        int sqr = (int) Math.sqrt(rules.length());
        HashMap<Object, Set<String>> all = new HashMap<>();
        for (int i = 0; i < rules.length(); i++) {
            for (int k = 0; k < rules.length(); k++) {
                if (!isEmpty(ques[i][k].value)) {
                    Set<String> h;
                    if (all.keySet().contains(i)) {
                        h = all.get(i);
                    } else {
                        h = new HashSet<>();
                    }
                    h.add(String.valueOf(ques[i][k].value));
                    all.put(i, h);


                    Set<String> l;
                    if (all.keySet().contains(rules.length() + k)) {
                        l = all.get(rules.length() + k);
                    } else {
                        l = new HashSet<>();
                    }
                    l.add(String.valueOf(ques[i][k].value));
                    all.put(rules.length() + k, l);

                    int index = i / sqr * sqr + k / sqr;

                    Set<String> q;
                    if (all.keySet().contains(rules.length() * 2 + index)) {
                        q = all.get(rules.length() * 2 + index);
                    } else {
                        q = new HashSet<>();
                    }

                    q.add(String.valueOf(ques[i][k].value));
                    all.put(index + rules.length() * 2, q);
                }
            }
        }
        for (int i = 0; i < all.size(); i++) {
            Set<String> s = all.get(i);
            if (s != null && s.size() == rules.length() - 1) {
                String value = rules;
                for (String v : s) {
                    value = value.replace(v, "");
                }
                if (i < rules.length()) {
                    for (int k = 0; k < rules.length(); k++) {
                        if (isEmpty(ques[i][k].value)) {
                            ques[i][k].value = value;
                            ques[i][k].writeTime = tag;
                            res = true;
                        }
                    }
                } else if (i < 2 * rules.length()) {
                    for (int k = 0; k < rules.length(); k++) {
                        if (isEmpty(ques[k][i - rules.length()].value)) {
                            ques[k][i - rules.length()].value = value;
                            ques[k][i - rules.length()].writeTime = tag;
                            res = true;
                        }
                    }
                } else {
                    int index = i - rules.length() * 2;
                    for (int k = 0; k < rules.length(); k++) {
                        int x = k % sqr + index / sqr * sqr;
                        int y = k / sqr + index % sqr * sqr;
                        if (isEmpty(ques[x][y].value)) {
                            ques[x][y].value = value;
                            ques[x][y].writeTime = tag;
                            res = true;
                        }
                    }
                }
            }
        }
        return res;
    }

    private static void printTag(Row[][] ques, int tag, String left, String right) {
        for (int i = 0; i < ques.length; i++) {
            for (int k = 0; k < ques[i].length; k++) {
                Row item = ques[i][k];
                if (k % 3 == 0) {
                    System.out.print("  ");
                }
                if (item.writeTime == tag) {
                    System.out.print(" " + left + item.value + right + " ");
                } else {
                    System.out.print("  " + item.value + "  ");
                }
            }
            if ((i - 2) % 3 == 0) System.out.println();
            System.out.println();
        }
    }

    private static boolean writeTwo(Row[][] lists, int tag) {
        Row[] newList = new Row[rules.length() * rules.length()];
        for (int i = 0; i < lists.length; i++) {
            System.arraycopy(lists[i], 0, newList, i * rules.length(), rules.length());
        }
        boolean hasChange = false;
        for (int i = 0; i < lists.length; i++) {
            for (int k = 0; k < lists[i].length; k++) {
                Row item = checkTwo(lists[i][k], lists, tag);
                if (item != null) {
                    item.writeTime = tag;
                    hasChange = true;
                }
            }
        }
        return hasChange;
    }


    private static boolean writeOne(Row[][] lists, int tag) {
        Row[] newList = new Row[rules.length() * rules.length()];
        for (int i = 0; i < lists.length; i++) {
            System.arraycopy(lists[i], 0, newList, i * rules.length(), rules.length());
        }
        boolean isChange = false;
        for (int i = 0; i < lists.length; i++) {
            for (int k = 0; k < lists[i].length; k++) {
                Row item = checkOne(lists[i][k], lists);
                if (item != null) {
                    item.writeTime = tag;
                    isChange = true;
                }
            }
        }
        return isChange;
    }

    /**
     * @param lists
     * @param tag
     * @return
     */
    public static Row checkTwo(Row checkItem, Row[][] lists, int tag) {
        if (!isEmpty(checkItem.value)) return null;
        boolean showLog = tag == 28 && checkItem.x == 0 && checkItem.y == 5;
        Set<Object> nonContent = new HashSet<>();
        Set<Object> mayContent = new HashSet<>();
        for (int i = 0; i < rules.length(); i++) {
            mayContent.add(Integer.valueOf(rules.substring(i, i + 1)));
        }
        for (int i = 0; i < lists.length; i++) {
            for (int k = 0; k < lists[i].length; k++) {
                Row item = lists[i][k];
                if (isEmpty(item.value)) continue;
                if (item.x == checkItem.x || item.y == checkItem.y || (item.sqrX == checkItem.sqrX && item.sqrY == checkItem.sqrY)) {
                    //同行.列.块内容
                    nonContent.add(item.value);
                }
            }
        }
        mayContent.removeAll(nonContent);
        if (showLog) {
            System.out.println("ShuDu-257.(" + checkItem.loc() + "):" + mayContent.toString());
        }
        int x = checkItem.x;
        int y = checkItem.y;
        for (Object integer : mayContent) {
            Set<String> notXLocation = new HashSet<>();
            Set<String> notYLocation = new HashSet<>();
            for (int i = 0; i < rules.length(); i++) {
                if (isEmpty(lists[x][i].value)) {
                    for (int m = 0; m < rules.length(); m++) {
                        if (showLog) {
                            System.out.println("ShuDu-268." + lists[m][i].value + "<>" + integer + ":" + isSame(lists[m][i].value, integer));
                        }
                        if (isSame(lists[m][i].value, integer)) {
                            notYLocation.add(lists[x][i].loc());
                            break;
                        }
                    }
                } else {
                    notYLocation.add(lists[x][i].loc());
                }
                if (isEmpty(lists[i][y].value)) {
                    for (int m = 0; m < rules.length(); m++) {
                        if (showLog) {
                            System.out.println("ShuDu-281." + lists[i][m].value + "<>" + integer + ":" + isSame(lists[i][m].value, integer));
                        }
                        if (isSame(lists[i][m].value, integer)) {
                            notXLocation.add(lists[i][y].loc());
                            break;
                        }
                    }
                } else {
                    notXLocation.add(lists[i][y].loc());
                }
            }
            if (showLog) {// TODO: 2023/11/3 有问题
                System.out.println("ShuDu-X." + integer + ":" + notXLocation.toString());
                System.out.println("ShuDu-Y." + integer + ":" + notYLocation.toString());
            }
            if (notXLocation.size() == rules.length() - 1 || notYLocation.size() == rules.length() - 1) {
                checkItem.value = integer;
                return checkItem;
            }

        }
        return null;
    }

    private static boolean isSame(Object one, Object two) {
        return !isEmpty(one) && !isEmpty(two) && one.equals(two);
//        if (show) {
//            System.out.println("ShuDu-one:" + one);
//            System.out.println("ShuDu-two:" + two);
//        }
//        return res;
    }

    /**
     * 数字找位置(以块为基本单位)
     *
     * @param checkItem
     * @param lists
     * @return
     */
    public static Row checkOne(Row checkItem, Row[][] lists) {
        if (!isEmpty(checkItem.value)) return null;
        Set<Object> nonContent = new HashSet<>();
        boolean showLog = checkItem.x == 1 && checkItem.y == 3;

        Set<Object> mayContent = new HashSet<>();
        for (int i = 0; i < rules.length(); i++) {
            mayContent.add(Integer.valueOf(rules.substring(i, i + 1)));
        }
        for (int i = 0; i < lists.length; i++) {
            for (int k = 0; k < lists[i].length; k++) {
                Row item = lists[i][k];
                if (isEmpty(item.value)) continue;
                if (item.x == checkItem.x || item.y == checkItem.y || (item.sqrX == checkItem.sqrX && item.sqrY == checkItem.sqrY)) {
                    //同行.列.块内容
                    nonContent.add(item.value);
                }
            }
        }

        mayContent.removeAll(nonContent);
        if (showLog) {
            System.out.println("ShuDu-375.(" + checkItem.loc() + ")." + mayContent);
        }
        Map<Object, Set> locations = new HashMap<>();

        for (Object integer : mayContent) {
            Set<String> notLocation = new HashSet<>();
            for (int i = 0; i < lists.length; i++) {
                for (int k = 0; k < lists[i].length; k++) {
                    Row item = lists[i][k];
                    if (item.sqrX != checkItem.sqrX && item.sqrY != checkItem.sqrY) continue;
                    if (isEmpty(item.value)) continue;
                    if (checkItem.sqrX == item.sqrX && checkItem.sqrY == item.sqrY) {
                        notLocation.add("(" + item.x + "," + item.y + ")");
                        continue;//同块数据
                    }
                    if (integer == item.value) {
                        if (item.sqrX == checkItem.sqrX) {//同行数据
                            notLocation.add("(" + item.x + "," + (int) (checkItem.sqrY * Math.sqrt(rules.length())) + ")");
                            notLocation.add("(" + item.x + "," + (int) (checkItem.sqrY * Math.sqrt(rules.length()) + 1) + ")");
                            notLocation.add("(" + item.x + "," + (int) (checkItem.sqrY * Math.sqrt(rules.length()) + 2) + ")");
                        } else {//同列数据
                            notLocation.add("(" + (int) (checkItem.sqrX * Math.sqrt(rules.length())) + "," + item.y + ")");
                            notLocation.add("(" + (int) (checkItem.sqrX * Math.sqrt(rules.length()) + 1) + "," + item.y + ")");
                            notLocation.add("(" + (int) (checkItem.sqrX * Math.sqrt(rules.length()) + 2) + "," + item.y + ")");
                        }
                    }
                }
            }
            if (locations.get(integer) == null) {
                locations.put(integer, notLocation);
            } else {
                Set<String> old = locations.get(integer);
                old.addAll(notLocation);
            }
            Set<String> mustNot = locations.get(integer);
            if (mustNot.size() == rules.length() - 1) {
                checkItem.value = integer;
                return checkItem;
            }
        }
        return null;
    }

    private final static String rules = "123456789";
    private final static Object[][] que = new Object[][]{
            {0, 8, 0, 9, 0, 0, 0, 3, 0},// {9, 0, 0, 0, 2, 0, 4, 0, 1},  //{0, 0, 6, 3, 2, 5, 0, 0, 1},    //{0, 5, 0, 0, 7, 0, 0, 4, 0},//
            {0, 0, 9, 1, 0, 0, 0, 0, 0},// {0, 0, 5, 0, 9, 0, 0, 2, 0},  //{3, 0, 0, 8, 1, 0, 0, 0, 5},    //{4, 0, 0, 0, 8, 9, 7, 0, 0},//
            {6, 0, 0, 0, 0, 0, 5, 0, 7},// {0, 4, 0, 1, 0, 0, 0, 9, 7},  //{1, 9, 2, 4, 7, 6, 3, 0, 8},    //{6, 7, 8, 3, 0, 0, 0, 0, 5},//
            {0, 0, 2, 5, 4, 0, 0, 0, 6},// {5, 0, 0, 0, 0, 1, 0, 0, 0},  //{0, 0, 0, 4, 1, 3, 0, 0, 9},    //{0, 6, 4, 0, 0, 0, 0, 3, 0},//
            {0, 3, 0, 0, 0, 2, 0, 0, 0},// {0, 0, 0, 0, 0, 0, 0, 0, 2},  //{6, 0, 0, 0, 0, 0, 0, 0, 2},    //{0, 1, 2, 0, 9, 6, 0, 0, 0},//
            {1, 7, 0, 0, 0, 0, 0, 0, 3},// {4, 0, 0, 5, 7, 0, 3, 0, 9},  //{0, 0, 5, 0, 2, 8, 0, 0, 0},    //{0, 9, 5, 0, 0, 0, 0, 6, 0},//
            {0, 0, 3, 0, 0, 0, 7, 0, 4},// {0, 5, 3, 0, 0, 2, 1, 8, 0},  //{0, 8, 0, 0, 0, 0, 1, 2, 3},    //{0, 0, 6, 4, 0, 0, 0, 0, 1},//
            {2, 0, 0, 3, 0, 8, 0, 6, 0},// {0, 0, 0, 0, 0, 0, 0, 0, 0},  //{0, 0, 4, 0, 0, 0, 5, 9, 7},    //{1, 4, 0, 0, 2, 8, 6, 0, 0},//
            {0, 0, 0, 0, 0, 0, 0, 0, 0} // {0, 0, 2, 8, 0, 0, 0, 0, 3}   //{5, 0, 0, 0, 3, 0, 6, 0, 4}     //{0, 8, 0, 0, 6, 0, 0, 2, 0} //
    };

    private static class Row {
        private Object value;
        private int x;//位置X
        private int y;//位置Y
        private int sqrX;//块位置X
        private int sqrY;//块位置Y
        private int writeTime = 0;
        private int sqr = (int) Math.sqrt(rules.length());

        public Row(Object o, int x, int y) {
            this.value = o;
            this.x = x;
            this.y = y;
            this.sqrX = x / sqr;
            this.sqrY = y / sqr;
        }

        private String loc() {
            return x + "," + y;
        }

        private String sqrLoc() {
            return sqrX + "," + sqrY;
        }

        private int lineIndex() {
            return x * 9 + y;
        }
    }

    /**
     * @return 验证结果是否正确
     */
    private static boolean isOk(Object[][] con) {
        if (con != null) {

            for (int i = 0; i < con.length; i++) {
                StringBuffer buffer = new StringBuffer();
                for (int k = 0; k < con[i].length; k++) {
                    if (con[i][k] instanceof Row) {
                        buffer.append(((Row) con[i][k]).value);
                    } else {
                        buffer.append(con[i][k]);
                    }
                }
                if (!isOk(buffer.toString())) {
                    System.out.println("error-H" + i + ">>" + buffer.toString());
                    return false;
                }
            }
            for (int i = 0; i < con.length; i++) {
                StringBuffer buffer = new StringBuffer();
                for (int k = 0; k < con[i].length; k++) {
                    if (con[k][i] instanceof Row) {
                        buffer.append(((Row) con[k][i]).value);
                    } else {
                        buffer.append(con[k][i]);
                    }
                }
                if (!isOk(buffer.toString())) {
                    System.out.println("error-L" + i);
                    return false;
                }
            }
            int l = (int) Math.sqrt(rules.length());

            for (int outI = 0; outI < l; outI++) {
                for (int outK = 0; outK < l; outK++) {
                    StringBuffer buffer = new StringBuffer();
                    for (int i = 0; i < l; i++) {
                        for (int k = 0; k < l; k++) {
                            if (con[i + outI * l][k + outK * l] instanceof Row) {
                                buffer.append(((Row) con[i + outI * l][k + outK * l]).value);
                            } else {
                                buffer.append(con[i + outI * l][k + outK * l]);
                            }
                        }
                    }
                    if (!isOk(buffer.toString())) {
                        System.out.println("error-S:(" + outI + "," + outK + ")");
                        return false;
                    }
//                    System.out.print("index:" + buffer);
//                    System.out.println();

                }
            }


        }
        return true;
    }

    private static boolean isEmpty(Object con) {
        return con == null || con instanceof String && "".equals(((String) con).trim()) || con instanceof Integer && (int) con == 0;
    }


    private static boolean isOk(String con) {
        for (int i = 0; i < rules.length(); i++) {
            if (!con.contains(rules.substring(i, i + 1))) {
                System.out.println("ShuDu-474:" + rules.substring(i, i + 1));
                return false;
            }
            if (!rules.contains(con.substring(i, i + 1))) {
                System.out.println("ShuDu-478:" + con.substring(i, i + 1));
                return false;
            }
        }
        return true;
    }
}
